/* 优先队列定义 */
typedef struct TreeNode *Tree;
struct TreeNode {
    Vertex idx; /* 顶点编号 */
    int lb; /* 下界函数值 */
    Tree parent; /* 指向该顶点在决策树中的父结点 */
    int cnt; /* 到达该顶点时，路径上的顶点数 */
};
typedef Tree HElemSet;
typedef int Position; /* 数组下标即为元素位置 */
typedef struct BinaryHeapNode *MinHeap;
struct BinaryHeapNode {
    HElemSet *data; /* 数据元素数组 */
    int size; /* 规模 */
    int capacity; /* 容量 */
};

#define kMaxPQSize 362880 /* 预估算法需要的队列规模为(n-1)! */

void InitPQueue(MinHeap pq, int capacity) {
    pq->capacity = capacity;
    pq->size = 0;
    /* 数据从下标1开始存储，需要多声明1个空间 */
    pq->data = (HElemSet *)malloc(sizeof(HElemSet) * (capacity + 1));
}

void SiftUp(MinHeap h, Position i) {
    HElemSet elem;

    elem = h->data[i];
    while (i > 1
            && elem->lb < h->data[i >> 1]->lb) { /* 当前结点小于其父结点 */
        h->data[i] = h->data[i >> 1]; /* 将i的父结点元素下移 */
        i >>= 1; /* i指向原结点的父结点，即向上调整 */
    }
    h->data[i] = elem;
}

void SiftDown(MinHeap h, Position i) {
    Position last, child;
    HElemSet elem;

    last = h->size; /* 这是最后一个元素的位置 */
    elem = h->data[i];
    while (1) {
        child = i << 1; /* child当前是i的左孩子的位置 */
        if (child < last
                && h->data[child + 1]->lb < h->data[child]->lb) { /* 如果i有右孩子并且右孩子更小 */
            child++; /* child更新为i的右孩子的位置 */
        } else if (child > last) { /* 如果i是叶子结点 */
            break; /* 已经调整到底，跳出循环 */
        }
        if (h->data[child]->lb < elem->lb) { /* 若较小的孩子比elem小 */
            h->data[i] = h->data[child]; /* 将较小的孩子结点上移 */
            i = child; /* i指向原结点的孩子结点，即向下调整 */
        } else { /* 若所有孩子都不比elem小 */
            break; /* 则找到了elem的最终位置，跳出循环 */
        }
    }
    h->data[i] = elem;
}

void Insert(MinHeap h, HElemSet x) {
    Position last;

    if (h->size == h->capacity) { /* 堆已满 */
        printf("错误：堆已满，无法插入。\n");
    } else {
        h->size++;
        last = h->size;
        h->data[last] = x; /* 暂时将x放入最后一个元素的位置 */
        SiftUp(h, last);
    }
}

HElemSet ExtractMin(MinHeap h) {
    HElemSet min_key;
    Position last;

    min_key = h->data[1]; /* 这是将要返回的最小元 */
    last = h->size; /* 这是删除前最后一个元素的位置 */
    h->size--;
    h->data[1] =
        h->data[last]; /* 暂时将删除前最后一个元素放入根的位置 */
    SiftDown(h, 1); /* 从根结点下调 */
    return min_key;
}

bool IsEmpty(MinHeap h) {
    return (h->size == 0);
}
/* 优先队列定义 结束 */

int Min(int x, int y) {
    return (x < y) ? x : y;
}

bool IsLeaf(MGraph graph, Tree u) {
    /* 判断u是否决策树中的叶结点 */
    /* 若根结点到u的路径上有全部n个结点 */
    /* 且u到起点0存在一条边 */
    /* 则u就是周游路线上的最后一个顶点，即决策树的叶结点 */
    return (u->cnt == graph->n_verts && ExistEdge(graph, u->idx, 0) == true);
}

int UpdateUB(MGraph graph, Tree u, int UB) {
    /* 周游路线全长 = 根到u的路径长度 + u到起点0的边长 */
    return Min(UB, u->lb + graph->edge_matrix[u->idx][0]);
}

bool IsNextV(MGraph graph, Tree u, Vertex v_idx) {
    /* 判断v_idx是否有可能是u扩展出来的下一个决策树结点 */
    bool ret;
    Tree w;

    ret = ExistEdge(graph, u->idx,
                    v_idx); /* 图中是否存在到v_idx的有向边 */
    for (w = u->parent; ret
            && w; w = w->parent) { /* 检查从u到树根的路径 */
        if (w->idx == v_idx) { /* 若v_idx已经存在于路径中 */
            ret = false; /* 则不可扩展 */
        }
    }
    return ret;
}

int LB(MGraph graph, Tree u, Vertex v_idx) {
    /* 计算v_idx顶点的下界函数值，u是其在决策树中的父结点 */
    return u->lb + graph->edge_matrix[u->idx][v_idx];
}